COMMENT ⊗   VALID 00004 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002			       Checkers on the Video-Brain
C00011 00003			 HOW the CHECKERS program plays Checkers
C00021 00004			    A brief history of computer games
C00025 ENDMK
C⊗;
		       Checkers on the Video-Brain

			       HOW TO PLAY

To play Checkers against the Video-Brain, Insert the Checkers cartridge,
plug one JOY STICK cord into socket 1 and push the start button.

The Video-Brain will respond by displaying the word CHECKERS for a moment
and then it will display the following,

			   CHOOSE          KEY
			    TOM              T
			    DICK             D
			    HARRY            H

and wait for you to type the letter T or D or H.  These refer to the skill
level desired, Robot Tom is the least skilled and should be selected until
you have had an opportunity to assess your relative skill as compared with
the Video-Brain. Robot HARRY is the best player of the three.

If any other key (including the space bar) is struck, the Video-Brain will
accept this as equivalent to the letter T.  This is done so that a young
child can be told to reply to all questions with the space bar.

The Video-Brain will next display,

		      YOU MOVE FIRST?         Y OR N

and then wait for you to type a Y or an N.  As before, any key other than
the N key will be accepted as a Y (children usually like to play first).

If you type Y, the checker board is shown with the Black pieces (for you)
at the bottom, the message YOUR MOVE is displayed, a small square spot
(called the cursor) will appear somewhere on the board and the Video-Brain
will wait for your first move.  You may have to move the Joy Stick lever
back and forth and up and down a few times before you will be able to see
the cursor.

If you type N, the Video-Brain will play BLACK and it will play first.
Your (RED) pieces will appear at the bottom of the screen.  Note that your
pieces are always those that initially appear at the bottom of the screen
and that your non-king pieces can only move in the upward direction.

It is easy to learn to play checkers with the Video-Brain, even if you do
not know the game.  The Video-Brain will not let you make illegal moves,
and it will usually tell you what you are doing wrong.  The basic rules
are listed in the last paragraph of this explanation.

Moves are made by using the JOY STICK to move the cursor until it is
brought to rest on a piece that you wish to move.  You may have to
practice before you will be able to do this easily.  When you have the
cursor properly centered on the piece you want to move, you push the HIT
button on the side of the JOY STICK case.  If the selected piece can move,
the cursor spot will begin to blink.  If the selected piece cannot move, a
message will inform you of this fact and you must selest a different
piece.

Having selected a piece that can move, you again move the JOY STICK and an
additional cursor spot will appear which you move to the square where the
piece is to go.  With the cursor on this desired square you again press
the HIT BUTTON.  If the attempted move is a legal move, the piece will be
moved and the Video-Brain will begin to plan its move and it will display
the message

				 MY MOVE.

If you try to make an illegal move the Video-brain will tell you why it is
illegal and wait  for you  to make a  legal move.   After several  illegal
attempts the Video-Brain will cancel the piece selection and you must then
reselect the piece that you want to move.

Occasionally you may have a double jump (see explanation below).  To
make a double jump you make the first jump just as discribed above.  The
video-Brain will then prompt you by displaying
 	
			      CONTINUE JUMP

and you then move the cursor to the final position or if perchance you
have a triple jump then to the next "touch" point where the process is
repeated.

That's all there is  to it.  If you  are a good enough  player to get  the
best of the Video-Brain,  it will anticipate its  own defeat and tell  you
how many moves it  should take you  to win.  Conversely  if it expects  to
win, you are also told.

		       The basic rules of the game.

Checkers is a two person game played on a checker board in which the two
players take turns in moving one of their pieces.

The Video-Brain positions the pieces properly for you at the start of the
game.   The object  of the game  is to  get your opponent  in a  condition
where he cannot move, which you usually do by capturing all of his pieces.

Pieces are of two kinds, MEN and KINGS.  Your MEN can only move upward on
the screen while the Video-brain's MEN can only move downward.  MEN, when
they reach the last row in the direction that they can move are promoted
and become KINGS and can then move backward as well as forward.

Pieces move  along  diagonals, a  single square  at  a  time  except  when
"jumping" an opponent's piece.  Opponent's pieces are captured by jumping
them.

A jump move must be made whenever such a move is available.  To jump, you
must have one of your pieces in position next to an opponent's piece with
an empty square just beyond the opponent's piece, all of this along a
diagonal in a legal direction.  You then move your piece to this empty
square and the Video-Brain removes the captured piece.

Occasionally, it is possible (and also compulsory) to jump more than one
piece when the jumping piece lands on a square which puts it into a
position to make still another jump.  There is one exception to this rule:
a piece that is promoted on reaching the last row as a result of a jump
cannot continue to jump. If the jump condition remains after the opponent
has moved, then the jump becomes legal.
		 HOW the CHECKERS program plays Checkers

The checkers program plays  checkers very much the  way that you play  the
game, that is it  attempts to trace out  the consequences of its  proposed
moves with  due  allowance  for how  you  will  respond to  its  move  and
considering how it  will than be  able to  respond and what  you might  do
next, etc. for several moves in advance of the current position.  That is,
the program "looks ahead".

People sometimes think  that one could  simply store all  of the  possible
board situations with the desired replies, but this is quite impossible on
even the largest computer that could ever be built.

So the program looks  ahead.  But it  can look ahead for  only a very  few
moves,.  Again,  people quite  fail to  realize how  many different  board
positions would be involved if one tried to look ahead very far.  A simple
calculation will show what the problem is.

If we ignore jump moves to make the calculation easy we can quickly get  a
feeling for the difficulty.  Normally,  there are about 8 possible  moves,
so looking ahead  2 moves  involves considering  1 plus  8 plus  64 or  73
boards.  Four moves  ahead involves this  number of boards  plus 512  plus
4096 or 4618 boards. But now the numbers rapidly get out of hand because 8
moves ahead calls for over 18 million  boards and 16 moves calls for  over
300 million million boards!  These numbers are correct if one counts  only
the non-jump moves, but,  of courses, jump moves  will actually occur  and
more total moves will actually be played before these astronomical numbers
are reached.  Normal games usually go for more than 16 non-jump moves.

Most people find  it hard  to believe these  numbers because  they do  not
fully appreciate what is known in conmputer parlance as "the combinatorial
explosion" and  because  they  instinctively feel  that  there  could  not
possiblly be this many different board positions.  Actually there are  not
this many different board positions, many positions reached along one line
of play will be the same positions encountered along some other line,  but
the point is that they have to be looked at again before this fact becomes
known, and we are concerned  with the number of  times the boards must  be
examined.  The "combinatorial explosion" is real and it is encountered in
many different computer programs and much of the art of computer programming
consists of clever ways of dealing with it.

So the program can only look ahead a very few moves and certainly not  far
enough to see to the end of the game.

Having looked ahead a  few moves, the program  then tries to evaluate  the
resulting position.  If some pieces have  been captured by one side,  then
the sequence of  moves which lead  to this capture  is desirable for  this
side but,  of course,  not for  the other  side.  Sometimes  there are  no
captures and  then  the  evaluation consists  in  assessing  the  relative
strength of  the position:  for example,  whether one  side or  the  other
controls the center of the board.

Now after the  final board has  been evaluated, the  program must back  up
giving each side  (remember this  is all looking  ahead and  does not  yet
involve any actual moves) the chance  to replace the first chosen move  by
alternate choices, and again following this out to the practical limit  in
look  ahead  distance.   This  process  is  repeated  at  each  level   of
look-ahead, all the way back to the initial move.

If all of the moves that are considered  in this way are shown on a  piece
of paper  the resulting  picture looks  very  much like  a tree,  so  this
process is  called "backing  up  the tree".   Maybe  it should  be  called
"backing down the  tree" but for  some strange reason  the move trees  are
usually drawn up-side-down.

This backing up is done using a technique known in computer jargon as  the
"alpha-beta heuristic".  Don't  let this  jargon disturb  you because  you
already know this technique intuitively.   It simply means that you  cease
to consider all the remaining possible moves that your opponent might make
in response to  a move that  you are thinking  aboue as soon  as you  have
found that he  has one reply  that is greatly  to your disadvantage.   You
further assume that your opponent will do  the same from his or her  point
of view.  While you can do this without any great trouble it becomes quite
complicated to express this intuitive concept as a program for a  computer
which, of course, has no intuition.

The use of  the "alpha-beta heuristic"  results in a  great saving in  the
number of moves  that have  to be considers  because it  results in  "tree
pruning".  Without tree pruning, a computer would play very poor  checkers
indeed or else it would take centuries to make a single move.  People  who
are good at games are people who are good at "tree pruning".

Having explored  the complete  game  tree the  program then  selects  what
appears to be its best move and then waits for you to make your move.

So a computer plays checkers very much as you do.  The only difference  is
that it  must be  given a  very detailed  list of  instructions, called  a
computer program.   These instructions  are really  commands because  they
allow the computer no latitude at all  in its action.  It is told  exactly
what to do by the person who has prepared the program, but remember, it is
not told what  move to make  but it is  told how to  "look-ahead", how  to
"evaluate", how to "back up the tree", and how to "alpha-beta prune".

The proficiency  that the  computer  appears to  possess is  a  mechanical
reflection of  the  proficiency  of  the person  who  wrote  the  program,
subject, of  course,  to  the  constraints imposed  by  the  size  of  the
computer.  The checkers program on  the Video-brain cannot be expected  to
play as well as it would do on a multi-million dollar computer.  You may
be surprised to find how well it does play, so try it.
		    A brief history of computer games

There have been many attempts throughout history to construct machines
that could play games.  Most of the very early attempts were either
extremely crude or they were out-and-out frauds.

There was, for example, the very famous chess-playing machine constructed
in 1769 by the Baron Kempelen.  this was taken on tour all over the world,
and deceived thousands of people into thinking that it played the game
automatically, when in fact a small man was concealed inside.  Edger Allen
Poe described this machine in detail and it a is said to have defeated
Napoleon who was considered to be a very good player.

A chess playing machine, this time a real one, was constructed by Signor
Torres Quededo in about 1890 which played an end game of chess and which
with a rook and a king could checkmate an opponent with a single king.

As illustrated by these two examples, chess has been the principle game
that has attracted the designers of game playing machines almost from
beginning of history or at least as long as this game has been played.
However , there has been a great deal of work on other games, and
particularly on games such as Nim for which there exist complete
mathimatical solutions and on games such as Tic Tac Toe that are simple
enough to solve by considering all possible plays to the end of the
game.  We will have more to say about these games later.

An early attempt to construct what we today would call a Digital Computer
was made by the English mathematician, Charles Babbage. in 1833.  Charles
Babbage understood clearly all, or substantially all, of the fundimental
principles that are embodied in the modern digital computer, and remember,
this was in 1833.  Babbage was to spend the rest of his life in an
unsuccessful attempt to construct what he called his Analytical Engine.
This was long before the days of electronics and the machine had to be
constructed from mechanical parts, gears and levers, and the technology of
his day was simply not up to the task.  Indeed, even today it would be
quite impractical if we had to construct our computers entirely out of the
mechanical parts.

Babbage, not only understood the fundimental principles of the modern
computer, but he even proposed having his machine play chess.


Professor Samuel, who is primarily responsible for the Video-Brain
checkers program, became interested in the problem of programming
computers to play games in 1948.